0234. 回文链表【简单】
1. 📝 题目描述
给你一个单链表的头节点 head,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false。
示例 1:

txt
输入:head = [1,2,2,1]
输出:true1
2
2
示例 2:

txt
输入:head = [1,2]
输出:false1
2
2
提示:
- 链表中节点数目在范围
[1, 10^5]内 0 <= Node.val <= 9
进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
2. 🎯 s.1 - 数组解法(易理解)
js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
const values = []
let current = head
// 将链表值存储到数组中
while (current) {
values.push(current.val)
current = current.next
}
// 使用双指针判断数组是否为回文
let left = 0
let right = values.length - 1
while (left < right) {
if (values[left] !== values[right]) {
return false
}
left++
right--
}
return true
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
- 时间复杂度:
,需要遍历链表两次 - 空间复杂度:
,需要额外数组存储节点值 - 算法思路:
- 遍历链表,将所有节点值存储到数组中。
- 使用双指针从数组两端向中间比较,判断是否为回文。
3. 🎯 s.2 - 快慢指针 + 翻转链表(空间复杂度 O(1))
js
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function (head) {
if (!head || !head.next) return true
// 使用快慢指针找到链表中点
let slow = head
let fast = head
while (fast.next && fast.next.next) {
slow = slow.next
fast = fast.next.next
}
// 翻转后半部分链表
let secondHalf = reverseList(slow.next)
// 比较前半部分和翻转后的后半部分
let firstHalf = head
let result = true
while (secondHalf) {
if (firstHalf.val !== secondHalf.val) {
result = false
break
}
firstHalf = firstHalf.next
secondHalf = secondHalf.next
}
return result
}
// 辅助函数:翻转链表
function reverseList(head) {
let prev = null
let current = head
while (current) {
const next = current.next
current.next = prev
prev = current
current = next
}
return prev
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
- 时间复杂度:
,只需要遍历链表常数次 - 空间复杂度:
,只使用常数额外空间 - 算法思路:
- 找中点:
- 使用快慢指针,快指针每次走两步,慢指针每次走一步
- 当快指针到达末尾时,慢指针正好在中点位置
- 翻转后半部分:将链表从中点分开,翻转后半部分链表
- 比较两部分:同时遍历前半部分和翻转后的后半部分,比较对应节点值
- 恢复链表(可选):如果需要保持原链表结构,可以再次翻转后半部分进行恢复,不过这道题没有此要求
- 找中点: